【题解】[SDOI2017]数字表格莫比乌斯反演 luoguP3704

我们设 $n \leq m$ ，然后开始推式子，我们将 $gcd(i,j)$ 的值作为 “$d$” 提出来：

$\prod_{d=1}^{n}\prod_{i=1}^{n}\prod_{j=1}^{m}if(gcd(i,j)=d) f[d]$ $=\prod_{d=1}^{n}\prod_{i=1}^{n}\prod_{j=1}^{m}if(gcd(i,j)=d) f[d]$ $=\prod_{d=1}^{n}\prod_{i=1}^{ \lfloor\frac{n}{d}\rfloor }\prod_{j=1}^{ \lfloor\frac{m}{d}\rfloor }if(gcd(i,j)=1) f[d]$ $=\prod_{d=1}^{n} f[d]^{\sum_{i=1}^{ \lfloor\frac{n}{d}\rfloor }\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)=1]}$

$\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor }\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)=1]$ 是个熟悉的式子，我们从这个式子继续开刀：

$\sum_{i=1}^{ \lfloor\frac{n}{d}\rfloor }\sum_{j=1}^{ \lfloor\frac{m}{d}\rfloor }[gcd(i,j)=1]$ $=\sum_{i=1}^{ \lfloor\frac{n}{d}\rfloor }\sum_{j=1}^{ \lfloor\frac{m}{d}\rfloor }\sum_{x|gcd(i,j)} \mu(x)$ $=\sum_{x=1}^{n}\mu(x)\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dx}\rfloor$

于是原来的式子变成了：

$\prod_{d=1}^{n} f[d]^{\sum_{x=1}^{n}\mu(x)\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dx}\rfloor}$

设 $T=dx$ ，并将 $T$ 提出来枚举：

$\prod_{d=1}^{n} f[d]^{\sum_{x=1}^{n}\mu(x)\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dx}\rfloor}$ $=\prod_{T=1}^{n}\prod_{d|T} f[d]^{\mu( \lfloor\frac{T}{d}\rfloor )\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor}$ $=\prod_{T=1}^{n}(\prod_{d|T} f[d]^{\mu( \lfloor\frac{T}{d}\rfloor )})^{\lfloor\frac{n}{T}{\rfloor\lfloor\frac{m}{T}\rfloor}}$

这个样子多好啊，我们可以将可爱的 $(\prod_{d|T} f[d]^{\mu( \lfloor\frac{T}{d}\rfloor )})$ 预处理，也就是枚举每一个 $d$ ，然后将可以整除 $d$ 的每一个 $T$ 都算上 $d$ 带来的贡献即可。最后的时候可以整除分块。最终的时间复杂度为 $O(\sqrt{n})$ ，当然不算上预处理时候的复杂度，如果加上预处理的复杂度，最终的复杂度应该为 $O(N(log\ N+log\ mod)+T(\sqrt{n} \ log\ mod))$ ，$log\ mod$ 就是算逆元的复杂度。

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e6+2;
#define MOD 1000000007

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

bool vis[N+15];
int mui[N+15],inv[N+15],fib[N+15],sum[N+15],prime[N],cnt;
inline int pow(int x,int y) {
    int res=1;
    for(;y;y>>=1,x=1ll*x*x%MOD) if(y&1) res=1ll*res*x%MOD;
    return res%MOD;
}

inline void pre() {
    fib[1]=inv[1]=sum[0]=sum[1]=1;
    vis[1]=true,mui[1]=1;
    for(int i=2;i<=N;++i) {
        fib[i]=(fib[i-1]+fib[i-2])%MOD;
        inv[i]=pow(fib[i],MOD-2),sum[i]=1;
        if(!vis[i]) prime[++cnt]=i,mui[i]=-1;
        for(int j=1;j<=cnt&&i*prime[j]<=N;++j) {
            vis[i*prime[j]]=1;
            if(!(i%prime[j])) break;
            else mui[i*prime[j]]=-mui[i];
        }
    }
    for(int d=1;d<=N;++d) {
        if(!mui[d]) continue;
        for(int T=d;T<=N;T+=d) 
            sum[T]=1ll*sum[T]*(mui[d]==1?fib[T/d]:inv[T/d])%MOD;
    }
    for(int i=2;i<=N;++i) sum[i]=1ll*sum[i]*sum[i-1]%MOD;
    return;
}

int T,n,m;
int main() {
    pre(),IN(T);
    while(T--) {
        IN(n),IN(m);
        if(n>m) swap(n,m);
        int ans=1,res,num;
        for(int l=1,r=0;l<=n;l=r+1) {
            r=min(n/(n/l),m/(m/l));
            num=1ll*(n/l)*(m/l)%(MOD-1);
            res=1ll*sum[r]*pow(sum[l-1],MOD-2)%MOD;
            ans=1ll*ans*pow(res,num)%MOD;
        }
        printf("%d\n",(ans+MOD)%MOD);
    }
    return 0;
}

本文标题:【题解】[SDOI2017]数字表格莫比乌斯反演 luoguP3704

文章作者:Qiuly

发布时间:2019年04月10日 - 00:00

最后更新:2019年04月10日 - 22:10

原始链接:http://qiulyblog.github.io/2019/04/10/[题解]luoguP3704/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际转载请保留原文链接及作者。